home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Gold Collection / Software Vault - The Gold Collection (American Databankers) (1993).ISO / cdr49 / 112_01.zip / FGREP.C < prev    next >
Text File  |  1993-06-19  |  23KB  |  921 lines
  1. /* 
  2. HEADER:     CUG
  3. TITLE:        FGREP.C - Search File(s) for Fixed Patten(s)
  4. VERSION:    1.03
  5. DATE:        02/11/85
  6. DESCRIPTION:    "A full implementation of the UNIX 'fgrep'
  7.         utility. The algorithm used in this program
  8.         constructs a deterministic finite state automaton
  9.         (FSA) for pattern matching from the substrings,
  10.         then uses the FSA to process the text string in
  11.         one pass. The time taken to construct the FSA is
  12.         proportional to the sum of the lengths of the the
  13.         substrings. The number of state transitions made
  14.         by the FSA in processing the text string is
  15.         independent of the number of substrings."
  16. KEYWORDS:    fgrep, grep, filter, UNIX, pattern-matching
  17. SYSTEM:        Any
  18. FILENAME:    FGREP.C
  19. WARNINGS:    "The '-s' option may not be consistently
  20.         supported by various non-Unix operating systems
  21.         and compilers. Also, the Unix-specific '-b'
  22.         option of 'fgrep' is not supported. Finally,
  23.         non-Unix operating systems may not accept
  24.         lowercase character strings on the command line,
  25.         although these can be entered through files."
  26. CRC:        xxxx
  27. SEE-ALSO:    None
  28. AUTHORS:    Ian Ashdown - byHeart Software
  29. COMPILERS:    Any C compiler
  30. REFERENCES:    AUTHORS: Bell Telephone Laboratories;
  31.         TITLE:     UNIX Programmer's Manual Vol. 1, p. 166;
  32.         AUTHORS: A.V. Aho & M.J. Corasick;
  33.         TITLE:     'Efficient String Matching: An Aid to
  34.              Bibliographic Search'
  35.              Communications of the ACM
  36.              pp. 333 - 340, Vol. 18 No. 6 (June '75);
  37. ENDREF
  38. */
  39.  
  40. /*-------------------------------------------------------------*/
  41.  
  42. /* FGREP.C - Search File(s) For Fixed Pattern(s)
  43.  *
  44.  * Version 1.04          February 11th, 1985
  45.  *
  46.  * Modifications:
  47.  *
  48.  *   V1.00 (84/12/01)    - beta test release
  49.  *   V1.01 (85/01/01)    - added -P option
  50.  *            - improved command line validation
  51.  *   V1.02 (85/01/06)    - modified "run_fsa()" and "bd_move()"
  52.  *   V1.03 (85/02/11)    - added -S option
  53.  *
  54.  * Copyright 1985:    Ian Ashdown
  55.  *              byHeart Software
  56.  *              2 - 2016 West First Avenue
  57.  *              Vancouver, B.C. V6J 1G8
  58.  *              Canada
  59.  *
  60.  * This program may be copied for personal, non-commercial use
  61.  * only, provided that the above copyright notice is included in
  62.  * all copies of the source code. Copying for any other use
  63.  * without previously obtaining the written permission of the
  64.  * author is prohibited.
  65.  *
  66.  * pHILANTHROPICAL nOTES:
  67.  *
  68.  * Considerable time and effort went into the development of this
  69.  * software, which was expressly written for the public domain.
  70.  * The author will gladly accept any and all monetary
  71.  * contributions for the purpose of continuing such work!
  72.  *
  73.  * Notes:
  74.  *
  75.  * The algorithm used in this program constructs a deterministic
  76.  * finite state automaton (FSA) for pattern matching from the sub-
  77.  * strings, then uses the FSA to process the text string in one
  78.  * pass. The time taken to construct the FSA is proportional to
  79.  * the sum of the lengths of the the substrings. The number of
  80.  * state transitions made by the FSA in processing the text
  81.  * string is independent of the number of substrings.
  82.  *
  83.  * Algorithm Source:
  84.  *
  85.  * "Efficient String Matching: An Aid to Bibliographic Search"
  86.  * Alfred V. Aho & Margaret J. Corasick
  87.  * Communications of the ACM
  88.  * pp. 333 - 340, Vol. 18 No. 6 (June '75)
  89.  *
  90.  * USAGE: fgrep [-vclnhyefxps] [strings] <files>
  91.  *
  92.  * where:
  93.  *
  94.  *    -v    All lines but those matching are printed.
  95.  *    -c    Only a count of the matching lines is printed.
  96.  *    -l    The names of the files with matching lines are
  97.  *        listed (once), separated by newlines.
  98.  *    -n    Each line is preceded by its line number in the
  99.  *        file.
  100.  *    -h    Do not print filename headers with output lines.
  101.  *    -y    All characters in the file are mapped to upper
  102.  *        case before matching. (This is the default if the
  103.  *        string is given in the command line under CP/M,
  104.  *        as CP/M maps everything on the command line to
  105.  *        upper case. Use the -f option if you need both
  106.  *        lower and upper case.) Not a true UNIX "fgrep"
  107.  *        option (normally available under "grep" only),
  108.  *        but too useful to leave out.
  109.  *    -e    <string>. Same as a string argument, but useful
  110.  *        when the string begins with a '-'.
  111.  *    -f    <file>. The strings (separated by newlines) are
  112.  *        taken from a file. If several strings are listed
  113.  *        in the file, then a match is flagged if any of
  114.  *        the strings are matched. If -f is given, any
  115.  *        following argument on the command line is taken
  116.  *        to be a filename.
  117.  *    -x    Only lines matched in their entirety are printed.
  118.  *    -p    Each matched line is preceded by the matching
  119.  *        substring(s). Not a UNIX "fgrep" option, but too
  120.  *        useful to leave out.
  121.  *    -s    No output is produced, only status. Used when
  122.  *        when "fgrep" is run as a process that returns a
  123.  *        status value to its parent process. Under CP/M, a
  124.  *        non-zero value returned by "exit()" may terminate
  125.  *        a submit file that initiated the program,
  126.  *        although this is implementation-dependent.
  127.  *
  128.  * DIAGNOSTICS:
  129.  *
  130.  * Exit status is 0 if any matches are found, 1 if none, 2 for
  131.  * error condition.
  132.  *
  133.  * BUGS:
  134.  *
  135.  * The following UNIX-specific option is not supported:
  136.  *
  137.  *    -b    Each line is preceded by the block number in
  138.  *        which it was found
  139.  *
  140.  * Lines are limited to 256 characters.
  141.  *
  142.  */
  143.  
  144. /*** Definitions ***/
  145.  
  146. #define TRUE          -1
  147. #define FALSE           0
  148. #define MAX_LINE     257  /* Maximum number of characters */
  149.                   /* per line plus NULL delimiter */
  150. #define CP/M              /* Comment out for compilation */
  151.                   /* under UNIX */
  152.  
  153. #define CMD_ERR       0    /* Error codes */
  154. #define OPT_ERR       1
  155. #define INP_ERR       2
  156. #define STR_ERR       3
  157. #define MEM_ERR       4
  158.  
  159. /*** Typedefs ***/
  160.  
  161. typedef int BOOL;    /* Boolean flag */
  162.  
  163. /*** Data Structures ***/
  164.  
  165. /* Queue element */
  166.  
  167. typedef struct queue
  168. {
  169.   struct state_el *st_ptr;
  170.   struct queue *next_el;
  171. } QUEUE;
  172.  
  173. /* Transition element */
  174.  
  175. typedef struct transition
  176. {
  177.   char lchar;            /* Transition character */
  178.   struct state_el *nextst_ptr;    /* Transition state pointer */
  179.   struct transition *next_el;
  180. } TRANSITION;
  181.  
  182. /* FSA state element */
  183.  
  184. typedef struct state_el
  185. {
  186.   TRANSITION *go_ls;    /* Pointer to head of "go" list */
  187.   TRANSITION *mv_ls;    /* Pointer to head of "move" list */
  188.   struct state_el *fail_state;    /* "failure" transition state */
  189.   char *out_str;    /* Terminal state message (if any) */
  190. } FSA;
  191.  
  192. /*** Global Variables and Structures ***/
  193.  
  194. /* Dummy "failure" state */
  195.  
  196. FSA FAIL_STATE;
  197.  
  198. /* Define a separate data structure for State 0 of the FSA to
  199.  * speed processing of the input while the FSA is in that state.
  200.  * Since the Aho-Corasick algorithm only defines "go" transitions
  201.  * for this state (one for each valid input character) and no
  202.  * "failure" transitions or output messages, only an array of
  203.  * "go" transition state numbers is needed. The array is accessed
  204.  * directly, using the input character as the index.
  205.  */
  206.  
  207. FSA *MZ[128];    /* State 0 of FSA */
  208.  
  209. BOOL vflag = FALSE,    /* Command-line option flags */
  210.      cflag = FALSE,
  211.      lflag = FALSE,
  212.      nflag = FALSE,
  213.      hflag = FALSE,
  214.      yflag = FALSE,
  215.      eflag = FALSE,
  216.      fflag = FALSE,
  217.      xflag = FALSE,
  218.      pflag = FALSE,
  219.      sflag = FALSE;
  220.  
  221. /*** Include Files ***/
  222.  
  223. #include <stdio.h>
  224. #include <ctype.h>
  225.  
  226. /*** Main Body of Program ***/
  227.  
  228. int main(argc,argv)
  229. int argc;
  230. char **argv;
  231. {
  232.   char *temp;
  233.   BOOL match_flag = FALSE,
  234.        proc_file();
  235.   void bd_go(),
  236.        bd_move(),
  237.        error();
  238.  
  239.   /* Check for minimum number of command line arguments */
  240.  
  241.   if(argc < 2)
  242.     error(CMD_ERR,NULL);
  243.  
  244.   /* Parse the command line for user-selected options */
  245.  
  246.   while(--argc && (*++argv)[0] == '-' && eflag == FALSE)
  247.     for(temp = argv[0]+1; *temp != '\0'; temp++)    
  248.       switch(toupper(*temp))
  249.       {
  250.     case 'V':
  251.       vflag = TRUE;
  252.       break;
  253.     case 'C':
  254.       cflag = TRUE;
  255.       break;
  256.     case 'L':
  257.       lflag = TRUE;
  258.       break;
  259.     case 'N':
  260.       nflag = TRUE;
  261.       break;
  262.     case 'H':
  263.       hflag = TRUE;
  264.       break;
  265.     case 'Y':
  266.       yflag = TRUE;
  267.       break;
  268.     case 'E':
  269.       eflag = TRUE;
  270.       break;
  271.     case 'F':
  272.       fflag = TRUE;
  273.       break;
  274.     case 'X':
  275.       xflag = TRUE;
  276.       break;
  277.     case 'P':
  278.       pflag = TRUE;
  279.       break;
  280.     case 'S':
  281.       sflag = TRUE;
  282.       break;
  283.     default:
  284.       error(OPT_ERR,NULL);
  285.       }
  286.  
  287.   /* "pflag" can only be TRUE if the following flags are FALSE */
  288.  
  289.   if(vflag == TRUE || cflag == TRUE || lflag == TRUE ||
  290.       xflag == TRUE || sflag == TRUE)
  291.     pflag = FALSE;
  292.  
  293.   /* Check for string (or string file) argument */
  294.  
  295.   if(!argc)
  296.     error(CMD_ERR,NULL);
  297.  
  298.   /* Build the "go" transitions. */
  299.  
  300.   bd_go(*argv++);
  301.   argc--;
  302.  
  303.   /* Build the "failure" and "move" transitions */
  304.  
  305.   bd_move();
  306.  
  307.   /* Process each of the input files if not "stdin". */
  308.  
  309.   if(argc < 2)
  310.     hflag = TRUE;
  311.   if(!argc)
  312.   {
  313.     if(proc_file(NULL,FALSE) == TRUE && match_flag == FALSE)
  314.       match_flag = TRUE;
  315.   }
  316.   else
  317.     while(argc--)
  318.       if(proc_file(*argv++,TRUE) == TRUE && match_flag == FALSE)
  319.     match_flag = TRUE;
  320.  
  321.   /* Return status to the parent process. Status is zero if any
  322.    * matches are found, 1 if none. */
  323.  
  324.   if(match_flag == TRUE)
  325.     exit(0);
  326.   else
  327.     exit(1);
  328. }
  329.  
  330. /*** Functions and Procedures ***/
  331.  
  332. /* PROC_FILE() - Run the FSA on the input file "in_file". Returns
  333.  *         TRUE if a match was found, FALSE otherwise.
  334.  */
  335.  
  336. BOOL proc_file(in_file,prt_flag)
  337. char *in_file;
  338. BOOL prt_flag;
  339. {
  340.   char buffer[MAX_LINE],    /* Input string buffer */
  341.        *nl,
  342.        *index(),
  343.        *stoupper(),
  344.        *fgets();
  345.   long line_cnt = 0L,    /* Line counter */
  346.        mtch_cnt = 0L;    /* Matched line counter */
  347.   BOOL mtch_flag,    /* Matched line flag */
  348.        run_fsa();
  349.   FILE *in_fd,
  350.        *fopen();
  351.   void error();
  352.  
  353.   if(in_file != NULL)    /* A file was specified as the input */
  354.   {
  355.     if(!(in_fd = fopen(in_file,"r")))
  356.       error(INP_ERR,in_file);
  357.   }
  358.   else
  359.     in_fd = stdin;
  360.  
  361.   /* Read in a line at a time for processing */
  362.  
  363.   while(fgets(buffer,MAX_LINE,in_fd))
  364.   {
  365.     if(nl = index(buffer,'\n'))  /* Remove newline */
  366.       *nl = '\0';
  367. #ifdef CP/M
  368.     if(fflag == FALSE || yflag == TRUE)
  369.       stoupper(buffer);
  370. #else
  371.     if(yflag == TRUE)
  372.       stoupper(buffer);
  373. #endif
  374.     line_cnt++;        /* Increment the line counter */
  375.     if((mtch_flag = run_fsa(buffer)) == TRUE)
  376.       mtch_cnt++;    /* Increment matched line counter */
  377.     if(cflag == FALSE && lflag == FALSE && sflag == FALSE &&
  378.     ((mtch_flag == TRUE && vflag == FALSE) ||
  379.     (mtch_flag == FALSE && vflag == TRUE)))
  380.     {
  381.       if(hflag == FALSE && prt_flag == TRUE)
  382.     printf("%s: ",in_file);
  383.       if(nflag == TRUE)
  384.     printf("%05ld: ",line_cnt);
  385.       puts(buffer);
  386.     }
  387.   }
  388.   if(lflag == TRUE && mtch_cnt > 0)
  389.     printf("%s\n",in_file);
  390.   else if(cflag == TRUE && sflag == FALSE)
  391.     printf("%ld\n",mtch_cnt);
  392.   if(in_file != NULL)
  393.     fclose(in_fd);
  394.   if(mtch_cnt)        /* Match found */
  395.     return TRUE;
  396.   else            /* No match found */
  397.     return FALSE;
  398. }
  399.  
  400. /* RUN_FSA() - Run the finite state automaton with string "str"
  401.  *           as input. Return TRUE if match, FALSE otherwise.
  402.  */
  403.  
  404. BOOL run_fsa(str)
  405. register char *str;
  406. {
  407.   register FSA *st_ptr;
  408.   char *message = NULL;
  409.   BOOL msg_flag = FALSE;
  410.   FSA *go(),
  411.       *move();
  412.  
  413.   st_ptr = NULL;    /* Initialize FSA */
  414.   if(xflag == FALSE)
  415.   {
  416.     /* Process the next input character in the string */
  417.  
  418.     while(*str)
  419.     {
  420.       st_ptr = move(st_ptr,*str);
  421.  
  422.       /* Print terminal state message and update FSA */
  423.  
  424.       if(st_ptr == 0 && message)
  425.       {
  426.     printf("--> %s\n",message);
  427.     message = NULL;
  428.     st_ptr = move(st_ptr,*str);
  429.       }
  430.       str++;
  431.       if(st_ptr)
  432.     if(st_ptr->out_str)    /* Terminal state? */
  433.       if(pflag == TRUE)
  434.       {
  435.         /* Save terminal state message */
  436.  
  437.         message = st_ptr->out_str;
  438.         msg_flag = TRUE;
  439.       }
  440.       else
  441.         return TRUE;
  442.     }
  443.     if(message)  /* Print any remaining terminal state message */
  444.       printf("--> %s\n",message);
  445.     return msg_flag;
  446.   }
  447.   else    /* Match exact lines only */
  448.   {
  449.     while(*str)
  450.     {
  451.       st_ptr = go(st_ptr,*str++);
  452.       if(!st_ptr || st_ptr == &FAIL_STATE)
  453.     return FALSE;    /* Line not matched */
  454.     }
  455.     return TRUE;    /* Exact line matched */
  456.   }
  457. }
  458.  
  459. /* GO() - Process "litchar" and return a pointer to the FSA's
  460.  *      corresponding "go" transition state. If the character
  461.  *      is not in the FSA state's "go" transition list, then
  462.  *      return a pointer to FAIL_STATE.
  463.  */
  464.  
  465. FSA *go(st_ptr,litchar)
  466. FSA *st_ptr;
  467. register char litchar;
  468. {
  469.   register TRANSITION *current;
  470.  
  471.   /* If State 0, then access separate State 0 data structure of
  472.    * the FSA. Note that there are no failure states defined for
  473.    * any input to FSA State 0.
  474.    */
  475.  
  476.   if(!st_ptr)
  477.     return MZ[litchar];
  478.   else
  479.   {
  480.     /* Point to the head of the linked list of "go" transitions
  481.      * associated with the state.
  482.      */
  483.  
  484.     current = st_ptr->go_ls;
  485.  
  486.     /* Transverse the list looking for a match to the input
  487.      * character.
  488.      */
  489.  
  490.     while(current)
  491.     {
  492.       if(current->lchar == litchar)
  493.     break;
  494.       current = current->next_el;
  495.     }
  496.  
  497.     /* Null value for "current" indicates end of list was reached
  498.      * without having found match to input character.
  499.      */
  500.  
  501.     return current ? current->nextst_ptr : &FAIL_STATE;
  502.   }
  503. }
  504.  
  505. /* MOVE() - Process "litchar" and return a pointer to the FSA's
  506.  *        corresponding "move" transition state.
  507.  */
  508.  
  509. FSA *move(st_ptr,litchar)
  510. FSA *st_ptr;
  511. register char litchar;
  512. {
  513.   register TRANSITION *current;
  514.  
  515.   /* If State 0, then access separate State 0 data structure of
  516.    * the FSA.
  517.    */
  518.  
  519.   if(!st_ptr)
  520.     return MZ[litchar];
  521.   else
  522.   {
  523.     /* Point to the head of the linked list of "move" transitions
  524.      * associated with the state.
  525.      */
  526.  
  527.     current = st_ptr->mv_ls;
  528.  
  529.     /* Transverse the list looking for a match to the input
  530.      * character.
  531.      */
  532.  
  533.     while(current)
  534.     {
  535.       if(current->lchar == litchar)
  536.     break;
  537.       current = current->next_el;
  538.     }
  539.  
  540.     /* Null value for "current" indicates end of list was reached
  541.      * without having found match to input character. The
  542.      * returned pointer is then to State 0.
  543.      */
  544.  
  545.     return current ? current->nextst_ptr : NULL;
  546.   }
  547. }
  548.  
  549. /* BD_GO() - Build the "go" transitions for each state from the
  550.  *         command-line arguments.
  551.  */ 
  552.  
  553. void bd_go(str)
  554. char *str;
  555. {
  556.   register char litchar;
  557.   char *nl,
  558.        buffer[MAX_LINE],    /* Input string buffer */
  559.        *stoupper(),
  560.        *fgets(),
  561.        *index();
  562.   FILE *str_fd,
  563.        *fopen();
  564.   void error(),
  565.        enter();
  566.  
  567.   /* Initialize FSA State 0 "go" transition array so that every
  568.    * invocation of "go()" with "state" = 0 initially returns a
  569.    * pointer to FAIL_STATE.
  570.    */
  571.  
  572.   for(litchar = 1; litchar <= 127; litchar++)
  573.     MZ[litchar] = &FAIL_STATE;
  574.  
  575.   /* If the -f option was selected, get the newline-separated
  576.    * strings from the file "str" one at a time and enter them
  577.    * into the FSA. Otherwise, enter the string "str" into the
  578.    * FSA.
  579.    */
  580.  
  581.   if(fflag == TRUE)
  582.   {
  583.     if(!(str_fd = fopen(str,"r")))
  584.       error(STR_ERR,str);
  585.  
  586.     while(fgets(buffer,MAX_LINE,str_fd))
  587.     {
  588.       if(nl = index(buffer,'\n'))    /* Remove the newline */
  589.     *nl = '\0';
  590.       if(yflag == TRUE)
  591.     stoupper(buffer);
  592.       enter(buffer);
  593.     }
  594.     fclose(str_fd);
  595.   }
  596.   else
  597.   {
  598.     if(yflag == TRUE)
  599.       stoupper(buffer);
  600.     enter(str);
  601.   }
  602.  
  603.   /* For every input character that does not lead to a defined
  604.    * "go" transition from FSA State 0, set the corresponding
  605.    * element in the State 0 "go" transition array to indicate
  606.    * a "go" transition to State 0.
  607.    */
  608.  
  609.   for(litchar = 1; litchar <= 127; litchar++)
  610.     if(MZ[litchar] == &FAIL_STATE)
  611.       MZ[litchar] = NULL;
  612. }
  613.  
  614. /* ENTER() - Enter a string into the FSA by running each
  615.  *         character in turn through the current partially-
  616.  *         built FSA. When a failure occurs, add the remainder
  617.  *         of the string to the FSA as one new state per
  618.  *         character. (Note that '\0' can never be a valid
  619.  *         character - C uses it to terminate a string.)
  620.  */
  621.  
  622. void enter(str)
  623. char *str;
  624. {
  625.   FSA *s,
  626.       *go(),
  627.       *create();
  628.   TRANSITION *current,
  629.          *insert();
  630.   char *strsave();
  631.   register char *temp;
  632.   register FSA *st_ptr = NULL;    /* Start in FSA State 0 */
  633.   register FSA *nextst_ptr;
  634.   void error();
  635.  
  636.   /* Run each character in turn through partially-built FSA until
  637.    * a failure occurs.
  638.    */  
  639.  
  640.   temp = str;
  641.   while((s = go(st_ptr,*temp)) != &FAIL_STATE)
  642.   {
  643.     temp++;
  644.     st_ptr = s;
  645.   }
  646.  
  647.   /* Process the remainder of the string */
  648.  
  649.   while(*temp)
  650.   {
  651.     /* If a new state, then create a new state and insert
  652.      * transition character and "go" transition in current
  653.      * state. (Note special case of FSA State 0.)
  654.      */
  655.  
  656.     if(!st_ptr)
  657.       nextst_ptr = MZ[*temp++] = create();
  658.     else if(!(current = st_ptr->go_ls))
  659.     {
  660.       nextst_ptr = create();
  661.       st_ptr->go_ls = insert(nextst_ptr,*temp++);
  662.     }
  663.     else
  664.     {
  665.       /* ... or it was the character that the FSA returned a
  666.        * "failure" for. Find the tail of the current state's list
  667.        * of "go" transitions, create a new state and append it
  668.        * to the current state's "go" list.
  669.        */
  670.  
  671.       while(current->next_el)
  672.     current = current->next_el;
  673.       nextst_ptr = create();
  674.       current->next_el = insert(nextst_ptr,*temp++);
  675.     }
  676.     st_ptr = nextst_ptr;
  677.   }
  678.  
  679.   /* Make string terminal state's output message */
  680.  
  681.   st_ptr->out_str = strsave(str);
  682. }
  683.  
  684. /* INSERT() - Create a new "go" transition and return a pointer
  685.  *          to it.
  686.  */
  687.  
  688. TRANSITION *insert(st_ptr,litchar)
  689. FSA *st_ptr;
  690. char litchar;
  691. {
  692.   TRANSITION *current;
  693.   char *malloc();
  694.   void error();
  695.     
  696.   if(!(current = (TRANSITION *)malloc(sizeof(TRANSITION))))
  697.     error(MEM_ERR,NULL);
  698.   current->lchar = litchar;
  699.   current->nextst_ptr = st_ptr;
  700.   current->next_el = NULL;
  701.   return current;
  702. }
  703.  
  704. /* CREATE() - Create an FSA state and return a pointer to it. */
  705.  
  706. FSA *create()
  707. {
  708.   FSA *st_ptr;
  709.   char *malloc();
  710.   void error();
  711.  
  712.   if(!(st_ptr = (FSA *)malloc(sizeof(FSA))))
  713.     error(MEM_ERR,NULL);
  714.   st_ptr->go_ls = st_ptr->mv_ls = NULL;
  715.   st_ptr->fail_state = NULL;
  716.   st_ptr->out_str = NULL;
  717.   return st_ptr;
  718. }
  719.  
  720. /* BD_MOVE() - Build the "failure" and "move" transitions for
  721.  *           each state from the "go" transitions.
  722.  */
  723.  
  724. void bd_move()
  725. {
  726.   register char litchar;
  727.   register FSA *r,    /* Temporary FSA state pointers */
  728.            *s,
  729.            *t;
  730.   FSA *go(),
  731.       *move();
  732.   TRANSITION *current,
  733.          *insert();
  734.   QUEUE *first,        /* Pointer to head of queue */
  735.     *last;        /* Pointer to tail of queue */
  736.   void add_queue(),
  737.        delete_queue();
  738.  
  739.   last = first = NULL;    /* Initialize the queue of FSA states */
  740.  
  741.   /* For each input character with a "go" transition out of FSA
  742.    * State 0, add a pointer to the "go" state to the queue. Note
  743.    * that this will also serve as the "move" transition list for
  744.    * State 0.
  745.    */
  746.  
  747.   for(litchar = 1; litchar <= 127; litchar++)
  748.     if(s = go(NULL,litchar))
  749.       add_queue(&first,&last,s);
  750.  
  751.   /* While there are still state pointers in the queue, do ... */
  752.  
  753.   while(first)
  754.   {
  755.     /* Remove State "r" pointer from the head of the queue. */
  756.  
  757.     r = first->st_ptr;
  758.     delete_queue(&first);
  759.  
  760.     /* Skip (terminal) state with no "go" transitions" */
  761.  
  762.     if(!r->go_ls)
  763.       continue;
  764.  
  765.     /* Make "move" transition list for terminal state same as its
  766.      * "go" transition list.
  767.      */
  768.  
  769.     if(r->out_str)
  770.       r->mv_ls = r->go_ls;
  771.  
  772.     /* For every input to State "r" that has a "go" transition to
  773.      * State "s", do ...
  774.      */
  775.  
  776.     for(litchar = 1; litchar <= 127; litchar++)
  777.     {
  778.       if((s = go(r,litchar)) != &FAIL_STATE)
  779.       {
  780.     /* If a defined "go" transition exists for State "r" on
  781.      * on input "litchar", add a pointer to State "s" to the
  782.      * end of the queue.
  783.      */
  784.  
  785.     add_queue(&first,&last,s);
  786.  
  787.     /* Calculate the "failure" transition of State "s" using
  788.      * the following algorithm.
  789.      */
  790.  
  791.     t = r->fail_state;
  792.     while(go(t,litchar) == &FAIL_STATE)
  793.       t = t->fail_state;
  794.     s->fail_state = go(t,litchar);
  795.       }
  796.       else
  797.       {
  798.     /* ... otherwise set the pointer to State "s" to a
  799.      * pointer to the precalculated "move" transition of
  800.      * State "r"'s failure state on input "litchar".
  801.      */
  802.  
  803.     s = move(r->fail_state,litchar);
  804.       }
  805.  
  806.       /* Add State "s" as the "move" transition for State "r" on
  807.        * input "litchar" only if it is not State 0 and "r" is not
  808.        * a terminal state.
  809.        */
  810.  
  811.       if(s && !r->out_str)
  812.     if(!r->mv_ls)    /* First instance of the list? */
  813.       current = r->mv_ls = insert(s,litchar);
  814.     else        /* No, just another one ... */
  815.       current = current->next_el = insert(s,litchar);
  816.     }
  817.   }
  818. }
  819.  
  820. /* ADD_QUEUE() - Add an instance to the tail of a queue */
  821.  
  822. void add_queue(head_ptr,tail_ptr,st_ptr)
  823. QUEUE **head_ptr,
  824.       **tail_ptr;
  825. FSA *st_ptr;
  826. {
  827.   QUEUE *pq;
  828.   char *malloc();
  829.   void error();
  830.  
  831.   /* Allocate the necessary memory and set the variables. */
  832.  
  833.   if(!(pq = (QUEUE *)malloc(sizeof(QUEUE))))
  834.     error(MEM_ERR,NULL);
  835.  
  836.   pq->st_ptr = st_ptr;
  837.   pq->next_el = NULL;
  838.  
  839.   if(!*head_ptr)    /* First instance of the queue? */
  840.     *tail_ptr = *head_ptr = pq;
  841.   else            /* No, just another one ... */
  842.     *tail_ptr = (*tail_ptr)->next_el = pq;
  843. }
  844.  
  845. /* DELETE_QUEUE() - Delete an instance from the head of queue */
  846.  
  847. void delete_queue(head_ptr)
  848. QUEUE **head_ptr;
  849. {
  850.   *head_ptr = (*head_ptr)->next_el;
  851. }
  852.  
  853. /* STRSAVE() - Save a string somewhere in memory */
  854.  
  855. char *strsave(str)
  856. char *str;
  857. {
  858.   int strlen();
  859.   char *p,
  860.        *malloc();
  861.   void error();
  862.  
  863.   if(p = malloc(strlen(str) + 1))
  864.     strcpy(p,str);
  865.   else
  866.     error(MEM_ERR,NULL);
  867.   return p;
  868. }
  869.  
  870. /* STOUPPER() - Map entire string pointed to by "str" to upper
  871.  *        case.
  872.  */
  873.  
  874. char *stoupper(str)
  875. register char *str;
  876. {
  877.   register char *temp;
  878.  
  879.   temp = str;
  880.   while(*temp)
  881.     *temp++ = toupper(*temp);
  882.   return str;
  883. }
  884.  
  885. /* ERROR() - Error reporting. Returns an exit status of 2 to the
  886.  *         parent process.
  887.  */
  888.  
  889. void error(n,str)
  890. int n;
  891. char *str;
  892. {
  893.   fprintf(stderr,"\007\n*** ERROR - ");
  894.   switch(n)
  895.   {
  896.     case CMD_ERR:
  897.       fprintf(stderr,"Illegal command line");
  898.       break;
  899.     case OPT_ERR:
  900.       fprintf(stderr,"Illegal command line option");
  901.       break;
  902.     case INP_ERR:
  903.       fprintf(stderr,"Can't open input file %s",str);
  904.       break;
  905.     case STR_ERR:
  906.       fprintf(stderr,"Can't open string file %s",str);
  907.       break;
  908.     case MEM_ERR:
  909.       fprintf(stderr,"Out of memory");
  910.       break;
  911.     default:
  912.       break;
  913.   }
  914.   fprintf(stderr," ***\n\nUsage: fgrep [-vclnhyefxps]");
  915.   fprintf(stderr," [strings] <files>\n");
  916.   exit(2);
  917. }
  918.  
  919. /*** End of FGREP.C ***/
  920. OUPPER() - Map entire string pointed to by "str" to upper
  921.  *